googologywikiaorg-20200223-history
Talk:TREE sequence
Archive 1 should we redirect TREE(3) to TREE sequence? discuss here. i think yes. Cookiefonster (talk) 01:31, February 17, 2015 (UTC) Should we redirect TREE(3) to TREE sequence? Yes No I saw that for example Fish's numbers has been added to the full list twice. So, could other values of TREE(k) be in the list? I mean there certainely is values of k at wich TREE(k) would overpower for example Meameamealokkapoowa Oompa of Loader's Number, that would be cool to add a such number Fluoroantimonic Acid (talk) 18:52, June 4, 2015 (UTC)Trifluoromethanesulfonic Acid TREE(3) is the only value that is particularly notable, since it's the smallest nontrivial value of TREE(n) - TREE(1) and TREE(2) are 1 and 3 respectively. the next values aren't really in a different realm of numbers from TREE(3) if i'm not mistaken. the fish numbers are different, since each of them are really separately devised values and not just different outputs of a single function. Cookiefonster (talk) 19:24, June 4, 2015 (UTC) :Another thing is that other specific values of TREE(n) have never been (afaik) considered, so there is no reason to put different values of TREE into the list. LittlePeng9 (talk) 20:53, June 4, 2015 (UTC) \(ACA_0+\Pi_2^1-BI\) "How strong is \(ACA_0+\Pi_2^1-BI\)?" In another word, what's the least ordinal \(\alpha\) such that \(f_\alpha(n)\) eventually outgrows all functions provably recursive in \(ACA_0+\Pi_2^1-BI\)? {hyp/^,cos} (talk) 03:07, July 7, 2015 (UTC) :Let \omegan = \Sigma(n) . Now f_\omega(n) > \Sigma(n) and since f_\omega is above recursive, the answer is \alpha = \omega . To see that it's least such ordinal, observe that all ordinals less than \omega are natural numbers and FGH for them doesn't depend on FS. :I think more interesting question would be: "What's the least ordinal existence of which cannot be proved by ACA_0+\Pi_2^1-BI ?" :Ikosarakt1 (talk ^ ) 12:14, August 2, 2015 (UTC) ::Finding the PTO of \(ACA_0+\Pi_2^1-BI\) is a research-level problem for sure. -- ve 13:20, August 2, 2015 (UTC) ::I would guess that the PTO of \(ACA_0+\Pi_2^1-BI\) is \(\theta(\Omega^{\omega},0)\), but I do not have a reference for that. Deedlit11 (talk) 06:33, August 5, 2015 (UTC) Where does TREE(3) fit into the heirarchy on Bowers' infinity scrapers page? Jonathan Bowers (Hedrondude), best known for the BEAF notation has a webpage which expands upon the array notation to define large numbers: http://www.polytope.net/hedrondude/scrapers.htm It's clear from reading the available online information that TREE grows more slowly than Rayo's and other functions which are arbitrarily defined as largest number that is theoretically writeable using an n-state Turing machine or a mathematical language with n symbols. So, TREE(3) is smaller than Oblivion, Rayo's number, etc. But what about large numbers that have been written clearly, and not based on a linguistic algorithm? I have read that TREE(3) is smaller than Loader's number . Loader's number is computable; the README for Loader's code states that this is because because the Calculus of Constructions is not Turing-complete, so the program will eventually terminate. But Loader's number is still defined using a concept of "The largest number that can be stated in the language L in less than N symbols", where, in this case L is the Calculus of Constructions. Using "less than N symbols" in the definition of a function allows for larger numbers than any other known technique. But what about numbers that use an already-defined mathematical language (like BEAF) and a fixed number of symbols? Numbers such as meameamealokkapoowa oompa? Is TREE(3) smaller than meameamealokkapoowa oompa, or any other number defined using an expansion of up-arrow notation without the "less than N symbols" trick? I suspect that TREE(3) is smaller than oompa, but since I have trouble reading the notation of the fast-growing heriarchy, I would be curious to know approximately where it fits into Bowers' infinity scrapers page. For example assuming meameamealokkapoowa oompa beats it, is TREE(3) also smaller than a Gongulus? Bowers does not resort to using the phrase "defined in fewer than N symbols" until the definition of Oblivion at the very bottom of the page. :BEAF did not well-defined above the tetrational arrays. AarexWikia04 - 01:26, October 1, 2016 (UTC) :I think TREE(3) can be expressed in Sublegion BEAF \(\841 (Talk)\) 12:27, October 13, 2016 (UTC) :I can argue with AarexWikia04, saying that pentational arrays are also well-defined with work of Deedlit11 and Ikosarakt1. So, I dunno if pentational arrays should beat TREE (3), and I think that they don't. —Preceding unsigned comment added by Tetramur (talk • ) 11:23, May 2, 2019 (UTC) Value of Weak Tree Function I think that this section: A larger lower bound has since been found. Define \(\text{tree}_2(n)=\text{tree}^n(n)\) and \(\text{tree}_3(n)=\text{tree}_2^n(n)\). Then \(\text{TREE}(3) > \text{tree}_3(\text{tree}_2(\text{tree}(8)))\). The latter expression is equal to treetreetree...tree(n)...(n)(n)(n) with n layers, where \(n = \text{tree}^{\text{tree}(8)}(\text{tree}(8))\). is more accurately (and helpfully) written as this: A larger lower bound has since been found. Define \(\text{tree}_2(n)=\text{tree}^n(n)\) and \(\text{tree}_3(n)=\text{tree}_2^n(n)\). Then \(\text{TREE}(3) > \text{tree}_3(\text{tree}_2(\text{tree}(8)))\). The latter expression is equal to treetreetree...tree(n)...(n)(n)(n) with \(n^2\) layers, where \(n = \text{tree}^{\text{tree}(8)}(\text{tree}(8))\). I notice that \(\text{tree}_3(n)\) creates a tower of n \(\text{tree}_2(n)\)s, each level of which creates a tower of \(\text{tree}_2(n)\) \(\text{tree}\)s. The pattern shows that \(\text{tree}_m(n)\) creates a tower of \(n^{m-1}\) \(\{tree}\)s following FGH's \(f_2\)(n) growth rate (in the number of \(\text{tree}\) iterations. 13:01, December 24, 2016 (UTC) :treem(n) equals treem-1n(n); if you then expand the latter expression out in terms of treem-2(n), you get a tower of functional exponents of height n. Expanding it further to treem-3(n) would get you an ENORMOUS tower of functional exponents, much higher than n^2 or n^3; the actual height of the tower would be the previous exponential tower of treem-2(n), but height one less (so n-1). The value of that exponential tower of n-1 treem-2's would get you how high the exponential tower of treem-3 has to be. So things are a little more complicated. Deedlit11 (talk) 14:30, December 25, 2016 (UTC) How much larger is TREE(4) than TREE(3)? 01:06, January 26, 2017 (UTC) :Approximately TREE(4) larger 09:43, January 27, 2017 (UTC) Only TREE(3)? Why not TREE(4) or even TREETREE...(TREE10100(1000)(1000)? (TREEn+1(k)=TREEnk(k)) 19:39, November 14, 2017 (UTC) :One can of course talk about the values of TREE(n) for larger inputs. TREE(3) was notable in that it was the first value which jumped up really high: TREE(1) = 1, TREE(2) = 3, and TREE(3) requires going beyond the Small Veblen Ordinal to bound it in the fast-growing hierarchy using a reasonable number of symbols. Deedlit11 (talk) 03:43, November 17, 2017 (UTC) TREE(3) hits mainstream media! Popular Mechanics recently published an article on TREE(3) here: http://popularmechanics.com/science/math/a28725/number-tree3 (note: partially paywalled) --Ixfd64 (talk) 06:00, January 15, 2018 (UTC) :TREE(3) had already hit mainstream media in my opinion after the Numberphile video, but it's nice to know it is sinking it's roots into other places, (pun intended). Edwin Shade (talk) 16:12, January 15, 2018 (UTC) Growth rate of TREE function It's solved here, page 39. Definitions: Labeled tree A''' is homeomorphically embeddable into '''B if there exists such an injection f''' from nodes of '''A to nodes of B that #For any node s and t of A, f(the nearest common ancestor of s,t) is the nearest common ancestor of f(s), f(t). #For any node t of A, (the label of t, the label of f(t)) is "in certain ordering". If the labels of nodes are in a well-partial ordering (i.e. the "in certain ordering"), then the trees are also in a well-partial ordering by homeomorphically embedding. Further, if the labels of nodes have order type \(\alpha\), then the corresponding trees have order type \(\le\theta(\Omega^\omega\alpha,0)\). For TREE(n), the labels can be 1,2,...,n, and "in certain ordering" means "equal", so the labels form a well-partial ordering of type n. So the labeled trees have order type \(\le\theta(\Omega^\omega n,0)\). Here shows an ordering of \(\theta(\Omega^\omega n,0)\), so \(\text{TREE}(m,n)\approx f_{\theta(\Omega^\omega m,0)}(n)\) and \(\text{TREE}(n)\approx f_{\theta(\Omega^\omega\omega,0)}(n)\). Now we can say about upper bounds of TREE(3), e.g. \(f_{\theta(\Omega^\omega\omega,0)}(3)\). {hyp/^,cos} (talk) 04:03, May 31, 2018 (UTC) : I have discussed it with Plain'N'Simple on the estimation using the upperbound of the ordinal types, but could not derive the upperbound of TREE(3) in your way. How could you verify the upperbound of the value from the upperbound of the ordinal types? Please read issues in the thread here starting from my comment "That function employs the 2-adic encoding...". The upperbound of the ordinal types do not give even an upperbound of the growth rate using a canonical system of fundamental sequences. If you have some unwritten reasoning, please tell me. If you just mistook the argument, please clarify it since there are many reasonless statements on the upperbound of TREE(3), which might have been spread from this community. : p-adic 04:13, October 25, 2019 (UTC) Weak tree(3) bound by mgiroux and Deedlit It origins here, but I have calculated again and result a different value. :4. (()()()) :5. ((()())()) :6. ((((()())))) :7. ((((())(())))) :8. ((((((())))()))) tree 1 = () and n+1 = (n), then this can be written as (((4 1))) :9. (((3 1))) :10. (((2 1))) :11. (((1 1))) :12. ((5 5)) :13. ((7 4)) :16. ((4 4)) :17. ((12 3)) :26. ((3 3)) :27. ((23 2)) :48. ((2 2)) :49. ((46 1)) :94. ((1 1)) :95. (47 47) :96. (49 46) :99. (46 46) (47 47) to here it takes 4 steps :100. (54 45) :109. (45 45) (46 46) to here it takes 10 steps :110. (65 44) :131. (44 44) (45 45) to here it takes 22 steps Generally, from (48-n 48-n) to (47-n 47-n) it takes \(3\cdot2^n-2\) steps, so from (47 47) to (1 1) it takes \(\sum_{n=1}^{46}(3\cdot2^n-2)=422212465065886\) steps. :422212465065981. (1 1) :422212465065982. 422212465065982 :844424930131963. 1 So my calculation results tree(3) ≥ 844424930131960. {hyp/^,cos} (talk) 15:02, October 29, 2018 (UTC)